{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minimum Number of Swaps to Make the Binary String Alternating"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #string"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minSwaps"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #构成交替字符串需要的最小交换次数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个二进制字符串 <code>s</code> ，现需要将其转化为一个 <strong>交替字符串</strong> 。请你计算并返回转化所需的 <strong>最小</strong> 字符交换次数，如果无法完成转化，返回<em> </em><code>-1</code><em> </em>。</p>\n",
    "\n",
    "<p><strong>交替字符串</strong> 是指：相邻字符之间不存在相等情况的字符串。例如，字符串 <code>\"010\"</code> 和 <code>\"1010\"</code> 属于交替字符串，但 <code>\"0100\"</code> 不是。</p>\n",
    "\n",
    "<p>任意两个字符都可以进行交换，<strong>不必相邻</strong> 。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"111000\"\n",
    "<strong>输出：</strong>1\n",
    "<strong>解释：</strong>交换位置 1 和 4：\"1<em><strong>1</strong></em>10<em><strong>0</strong></em>0\" -> \"1<em><strong>0</strong></em>10<em><strong>1</strong></em>0\" ，字符串变为交替字符串。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"010\"\n",
    "<strong>输出：</strong>0\n",
    "<strong>解释：</strong>字符串已经是交替字符串了，不需要交换。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"1110\"\n",
    "<strong>输出：</strong>-1\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 <= s.length <= 1000</code></li>\n",
    "\t<li><code>s[i]</code> 的值为 <code>'0'</code> 或 <code>'1'</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minimum-number-of-swaps-to-make-the-binary-string-alternating](https://leetcode.cn/problems/minimum-number-of-swaps-to-make-the-binary-string-alternating/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minimum-number-of-swaps-to-make-the-binary-string-alternating](https://leetcode.cn/problems/minimum-number-of-swaps-to-make-the-binary-string-alternating/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"111000\"', '\"010\"', '\"1110\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        a = s.count('1')\n",
    "        b = n - a\n",
    "        if abs(a - b) > 1:\n",
    "            return -1\n",
    "        \n",
    "        def f(x):\n",
    "            res = 0\n",
    "            for ch in s:\n",
    "                if int(ch) != x:\n",
    "                    res += 1\n",
    "                x ^= 1\n",
    "            return res\n",
    "\n",
    "        if a == b:\n",
    "            return min(f(1), f(0)) // 2\n",
    "        elif a > b:\n",
    "            return f(1) // 2\n",
    "        else:\n",
    "            return f(0) // 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        counter = Counter(c for c in s)\n",
    "        if abs(counter['0'] - counter['1']) > 1: return -1\n",
    "        # 默认 0 开头，否则 n  - needSwap\n",
    "        exp = 1\n",
    "        cnt = 0\n",
    "        for c in s:\n",
    "            if int(c) == exp: cnt += 1\n",
    "            exp = 1 - exp\n",
    "        \n",
    "        a, b = cnt, n - cnt\n",
    "        if a % 2 == 1 and b % 2 == 1: return -1\n",
    "        if a % 2 == 0 and b % 2 == 0: return min(a, b) // 2\n",
    "        return a // 2 if a % 2 == 0 else b // 2\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, s: str) -> int:\n",
    "        zeros = 0\n",
    "        ones = 0\n",
    "        for c in s:\n",
    "            if(c == '0'):\n",
    "                zeros += 1\n",
    "            else:\n",
    "                ones += 1\n",
    "        if(abs(zeros-ones) > 1):\n",
    "            return -1\n",
    "        result = 0\n",
    "        if(zeros > ones):\n",
    "            for i in range(len(s)):\n",
    "                if(s[i] == '1' and i % 2 == 0):\n",
    "                    result += 1\n",
    "        elif(zeros < ones):\n",
    "            for i in range(len(s)):\n",
    "                if(s[i] == '1' and i % 2 == 1):\n",
    "                    result += 1\n",
    "        else:\n",
    "            res1 = 0\n",
    "            for i in range(len(s)):\n",
    "                if(s[i] == '1' and i % 2 == 1):\n",
    "                    res1 += 1\n",
    "            res2 = 0\n",
    "            for i in range(len(s)):\n",
    "                if(s[i] == '1' and i % 2 == 0):\n",
    "                    res2 += 1\n",
    "            result = min(res1, res2)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, s: str) -> int:\n",
    "        cnt1 = s.count('1')\n",
    "        cnt2 = len(s) - cnt1\n",
    "        if abs(cnt1 - cnt2) > 1:\n",
    "            return -1\n",
    "\n",
    "        cnt = [0, 0]    # 第一位表示开头为1时不同的数量，第二位表示开头为0时不同的数量\n",
    "        for i, c in enumerate(s):\n",
    "            # 偶数为1，给1加，偶数为0，给0加。奇数为1，给0加，奇数为0，给1加\n",
    "            cnt[i & 1 ^ int(c)] += 1\n",
    "        if cnt1 > cnt2:\n",
    "            return cnt[0] + 1 >> 1\n",
    "        elif cnt1 == cnt2:\n",
    "            return min(cnt) + 1 >> 1\n",
    "        return cnt[1] + 1 >> 1\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        cnt= Counter(s)\n",
    "        if abs(cnt[\"0\"]-cnt[\"1\"]) > 1:\n",
    "            return -1\n",
    "        m = n//2\n",
    "        rest = n-2*m\n",
    "        ans = inf\n",
    "        for t in [\"01\"*m+\"0\"*rest, \"10\"*m+\"1\"*rest]:\n",
    "            if Counter(t) == cnt:\n",
    "                cur = sum(s[i]!=t[i] for i in range(n))\n",
    "                if cur //2 <ans:\n",
    "                    ans = cur//2\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        a = s.count(\"0\")\n",
    "        b = n-a\n",
    "        if abs(a-b)>1:return -1\n",
    "        if a>b:\n",
    "            temp = 0\n",
    "            # 0比1多\n",
    "            for i in range(0,n,2):\n",
    "                if s[i] != \"0\":\n",
    "                    temp+=1\n",
    "            return temp\n",
    "        elif b>a:\n",
    "            temp = 0\n",
    "            for i in range(0,n,2):\n",
    "                if s[i]!=\"1\":\n",
    "                    temp+=1\n",
    "            return temp\n",
    "        else:\n",
    "            temp = 0\n",
    "            for i in range(0,n,2):\n",
    "                if s[i]=='0':\n",
    "                    temp+=1\n",
    "            return min(temp,n//2-temp)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, s: str) -> int:\n",
    "        ans = 0x3f3f3f3f\n",
    "        n = len(s)\n",
    "        num_zeros = s.count('0')\n",
    "        num_ones  = n - num_zeros\n",
    "        if abs(num_ones - num_zeros) > 1:\n",
    "            return -1\n",
    "        target = 0        \n",
    "        cnt = 0\n",
    "        for c in s:\n",
    "            if int(c) != target: cnt += 1\n",
    "            target = 1 - target\n",
    "        if cnt % 2 == 0:\n",
    "            ans = min(ans, cnt // 2)\n",
    "        cnt = 0\n",
    "        target = 1\n",
    "        for c in s:\n",
    "            if int(c) != target: cnt += 1\n",
    "            target = 1 - target       \n",
    "        if cnt % 2 == 0:\n",
    "            ans = min(ans, cnt // 2)\n",
    "        return ans\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    \"\"\"\r\n",
    "        只有兩種情況: 010101... or 101010...\r\n",
    "        分別計算兩種情況的交換次數, 取最小值\r\n",
    "    \"\"\"\r\n",
    "    def minSwaps(self, s: str) -> int:\r\n",
    "        n = len(s)\r\n",
    "        cnt0_0 = cnt0_1 = 0 # 010101... 0->1, 1->0\r\n",
    "        cnt1_0 = cnt1_1 = 0 # 101010... 0->1, 1->0\r\n",
    "        for idx, ch in enumerate(s):\r\n",
    "            if idx % 2 == 0:\r\n",
    "                if ch == '0':\r\n",
    "                    cnt1_0 += 1 # '1'01010... 0->1\r\n",
    "                else:\r\n",
    "                    cnt0_1 += 1 # '0'10101... 1->0\r\n",
    "            else:\r\n",
    "                if ch == '0':\r\n",
    "                    cnt0_0 += 1 # 0'1'0101... 0->1\r\n",
    "                else:\r\n",
    "                    cnt1_1 += 1 # 1'0'1010... 1->0\r\n",
    "        if cnt0_0 == cnt0_1 and cnt1_0 == cnt1_1:\r\n",
    "            return min(cnt0_0, cnt1_0)\r\n",
    "        elif cnt0_0 == cnt0_1:\r\n",
    "            return cnt0_0\r\n",
    "        elif cnt1_0 == cnt1_1:\r\n",
    "            return cnt1_0\r\n",
    "        else:\r\n",
    "            return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        ones, zeros = 0, 0\n",
    "        odd = [0] * 2 \n",
    "        for i in range(n):\n",
    "            ones += int(s[i] == '1')\n",
    "            zeros += int(s[i] == '0')\n",
    "            if i % 2 == 0:\n",
    "                odd[0] += int(s[i] == '0')\n",
    "                odd[1] += int(s[i] == '1')\n",
    "            \n",
    "        if abs(ones- zeros) > 1:\n",
    "            return -1 \n",
    "        if n % 2 == 0:\n",
    "            return min(odd[0], odd[1]) \n",
    "        elif ones > zeros:\n",
    "            return odd[0] \n",
    "        else:\n",
    "            return odd[1] \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, s: str) -> int:\n",
    "        count0, count1 = 0, 0\n",
    "        for c in s:\n",
    "            if c == '1':\n",
    "                count1 += 1\n",
    "            else:\n",
    "                count0 += 1\n",
    "        \n",
    "        if abs(count0 - count1) > 1:\n",
    "            return -1\n",
    "        \n",
    "        res = len(s)\n",
    "        res1 = 0\n",
    "        if count0 >= count1:\n",
    "            for i in range(0, len(s), 2):\n",
    "                if s[i] != '0':\n",
    "                    res1 += 1\n",
    "            res = min(res, res1)\n",
    "        res2 = 0\n",
    "        if count1 >= count0:\n",
    "            for i in range(0, len(s), 2):\n",
    "                if s[i] != '1':\n",
    "                    res2 += 1\n",
    "            res = min(res, res2)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, s: str) -> int:\n",
    "        cnt = [0, 0]    # 第一位表示开头为1时不同的数量，第二位表示开头为0时不同的数量\n",
    "        c1 = 0\n",
    "        for i, c in enumerate(s):\n",
    "            # 偶数为1，给1加，偶数为0，给0加。奇数为1，给0加，奇数为0，给1加\n",
    "            cnt[i & 1 ^ int(c)] += 1\n",
    "            if c == '1':\n",
    "                c1 += 1\n",
    "\n",
    "        c0 = len(s) - c1\n",
    "        if abs(c1 - c0) > 1:\n",
    "            return -1\n",
    "        if c1 > c0:\n",
    "            diff = cnt[0]\n",
    "        elif c1 == c0:\n",
    "            diff = min(cnt)\n",
    "        else:\n",
    "            diff = cnt[1]\n",
    "        return diff + 1 >> 1\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, s: str) -> int:\n",
    "        slen = len(s)\n",
    "        s1 = slen//2\n",
    "        s1_n = 0\n",
    "        s0_n = 0\n",
    "        n1 = 0\n",
    "        for i in range(slen):\n",
    "            if s[i] == \"1\":\n",
    "                n1+=1\n",
    "        if slen%2 == 1:\n",
    "            if n1 > slen//2+1 or n1 < slen//2:\n",
    "                return -1\n",
    "        else:\n",
    "            if n1 != slen//2:\n",
    "                return -1\n",
    "        #由1开始进行遍历\n",
    "        flag = True\n",
    "        for i in range(slen):\n",
    "            if flag:\n",
    "                if s[i] != \"1\":\n",
    "                    s1_n+=1\n",
    "                flag = False\n",
    "            else:\n",
    "                if s[i] != \"0\":\n",
    "                    s1_n+=1\n",
    "                flag = True\n",
    "        \n",
    "        flag = False\n",
    "        for i in range(slen):\n",
    "            if flag:\n",
    "                if s[i] != \"1\":\n",
    "                    s0_n+=1\n",
    "                flag = False\n",
    "            else:\n",
    "                if s[i] != \"0\":\n",
    "                    s0_n+=1\n",
    "                flag = True\n",
    "\n",
    "        if s1_n%2 == 1 and s0_n%2 == 1:\n",
    "            return -1\n",
    "        if s1_n%2 == 1 and s0_n%2 == 0:\n",
    "            return s0_n//2                    \n",
    "        if s1_n%2 == 0 and s0_n%2 == 1:\n",
    "            return s1_n//2\n",
    "        return s1_n//2 if s1_n//2<s0_n//2 else s0_n//2      "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, s: str) -> int:\n",
    "        cnt1 = s.count('1')\n",
    "        cnt2 = len(s) - cnt1\n",
    "        if abs(cnt1 - cnt2) > 1:\n",
    "            return -1\n",
    "\n",
    "        cnt = [0, 0]    # 第一位表示开头为1时不同的数量，第二位表示开头为0时不同的数量\n",
    "        for i, c in enumerate(s):\n",
    "            # 偶数为1，给1加，偶数为0，给0加。奇数为1，给0加，奇数为0，给1加\n",
    "            cnt[i & 1 ^ int(c)] += 1\n",
    "\n",
    "        if cnt1 > cnt2:\n",
    "            diff = cnt[0]\n",
    "        elif cnt1 == cnt2:\n",
    "            diff = min(cnt)\n",
    "        else:\n",
    "            diff = cnt[1]\n",
    "        return diff + 1 >> 1\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, s: str) -> int:\n",
    "        c0 = c1 = a = b = 0\n",
    "        for i, c in enumerate(s):\n",
    "            c0 += c == '0'\n",
    "            c1 += c == '1'\n",
    "            a += i & 1 == 0 and c != '0'\n",
    "            b += i & 1 == 0 and c != '1'\n",
    "        # 不存在解\n",
    "        if abs(c0 - c1) > 1: return -1\n",
    "        return min(a, b) if c0 == c1 else (a if c0 > c1 else b)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, s: str) -> int:\n",
    "      cnt = 0\n",
    "      first = s[0]\n",
    "      n = len(s)\n",
    "      ans1 = 0\n",
    "      ans2 = 0\n",
    "      for i in range(0, n):\n",
    "        if s[i] == first:\n",
    "          cnt += 1\n",
    "        else:\n",
    "          cnt -= 1\n",
    "        if i % 2 == 0 and s[i] != first:\n",
    "          # print(i)\n",
    "          ans1 += 1\n",
    "        if i % 2 == 0 and s[i] == first:\n",
    "          ans2 += 1\n",
    "      ans = ans1 if cnt > 0 else ans2\n",
    "      if cnt == 0:\n",
    "        ans = min(ans1, ans2)\n",
    "      if abs(cnt) > 1:\n",
    "        ans = -1\n",
    "      return  ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, s: str) -> int:\n",
    "        # 统计0，1个数\n",
    "        zeros, ones = s.count('0'), s.count('1')\n",
    "        # 无法满足要求的情况\n",
    "        if (zeros - ones) > 1 or (ones - zeros) > 1:\n",
    "            return -1\n",
    "        n = len(s)\n",
    "        # 已经达到要求的情况\n",
    "        if n == 1:\n",
    "            return 0\n",
    "        res1, res2 = float(inf), float(inf)\n",
    "        # 0101\n",
    "        if zeros >= ones:\n",
    "            tmp = '0b'\n",
    "            tmp += '01' * ones\n",
    "            tmp += '0'\n",
    "            a = int(s, 2)\n",
    "            b = int(tmp, 2)\n",
    "            c = str(bin(a ^ b))\n",
    "            res1 = c.count('1') // 2            \n",
    "        # 1010\n",
    "        if ones >= zeros:\n",
    "            res2 = 0\n",
    "            tmp = '0b'\n",
    "            tmp += '10' * zeros\n",
    "            tmp += '1'\n",
    "            a = int(s, 2)\n",
    "            b = int(tmp, 2)\n",
    "            c = str(bin(a ^ b))\n",
    "            res2 = c.count('1') // 2\n",
    "            \n",
    "        return min(res1, res2)\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, s: str) -> int:\n",
    "        c0, c1 = s.count(\"0\"), s.count(\"1\")\n",
    "        if c0 + 1 < c1:\n",
    "            return -1\n",
    "        elif c0 + 1 == c1:\n",
    "            ans = 0\n",
    "            for i in range(0, len(s), 2):\n",
    "                if s[i] != \"1\":\n",
    "                    ans += 1\n",
    "            return ans\n",
    "        elif c0 == c1:\n",
    "            ans1 = 0\n",
    "            for i in range(0, len(s), 2):\n",
    "                if s[i] == \"0\":\n",
    "                    ans1 += 1\n",
    "            ans2 = len(s) // 2 - ans1\n",
    "            return min(ans1, ans2)\n",
    "        elif c0 == c1 + 1:\n",
    "            ans = 0\n",
    "            for i in range(0, len(s), 2):\n",
    "                if s[i] != \"0\":\n",
    "                    ans += 1\n",
    "            return ans\n",
    "        else:  # c0 > c1 + 1\n",
    "            return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, s: str) -> int:\n",
    "        ans = inf\n",
    "        c0 = c1 = 0\n",
    "        for i, x in enumerate(s):\n",
    "            if i % 2 and x == '0':\n",
    "                c0 += 1\n",
    "            if i % 2 == 0 and x == '1':\n",
    "                c1 += 1\n",
    "        if c0 == c1:\n",
    "            ans = min(ans, c0)\n",
    "        c0 = c1 = 0\n",
    "        for i, x in enumerate(s):\n",
    "            if i % 2 and x == '1':\n",
    "                c0 += 1\n",
    "            if i % 2 == 0 and x == '0':\n",
    "                c1 += 1\n",
    "        if c0 == c1:\n",
    "            ans = min(ans, c0)            \n",
    "        return ans if ans < inf else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, s: str) -> int:\n",
    "        cnt0, cnt1 = s.count('0'), s.count('1')\n",
    "        n = len(s)\n",
    "        if not ((n % 2 and abs(cnt0 - cnt1) == 1) or (n % 2 == 0 and cnt0 == cnt1)):\n",
    "            return -1 \n",
    "        \n",
    "        if n % 2 == 0:\n",
    "            t1 = '01' * (n // 2)\n",
    "            t2 = '10' * (n // 2)\n",
    "        else:\n",
    "            t1 = '01' * (n // 2) + '0'\n",
    "            t2 = '10' * (n // 2) + '1'\n",
    "        ans = n\n",
    "        c1 = sum(a != b for a, b in zip(s, t1))\n",
    "        if c1 % 2 == 0: ans = min(ans, c1 // 2)\n",
    "        c2 = sum(a != b for a, b in zip(s, t2))\n",
    "        if c2 % 2 == 0: ans = min(ans, c2 // 2)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, s: str) -> int:\n",
    "        sum_,cnt1,cnt2 = 0,0,0\n",
    "        for i in range(len(s)):\n",
    "            if s[i] == '0':\n",
    "                sum_ += 1\n",
    "            if i%2==0:\n",
    "                if s[i] == '1':\n",
    "                    cnt1 += 1\n",
    "                else:\n",
    "                    cnt2 += 1\n",
    "            else:\n",
    "                if s[i] == '0':\n",
    "                    cnt1 += 1\n",
    "                else:\n",
    "                    cnt2 += 1\n",
    "        if abs(2*sum_ - len(s)) > 1:\n",
    "            return -1\n",
    "        else:\n",
    "            res = len(s)//2\n",
    "            if cnt1%2 == 0:\n",
    "                res = min(res,cnt1//2)\n",
    "            if cnt2%2 == 0:\n",
    "                res = min(res,cnt2//2)\n",
    "            return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        c1 = s.count('1')\n",
    "        c2 = n - c1\n",
    "        if abs(c1-c2) > 1:\n",
    "            return -1\n",
    "        if c1 == c2:\n",
    "            return min(s[::2].count('0'), s[1::2].count('0'))\n",
    "        elif c1 < c2:\n",
    "            return s[::2].count('1')\n",
    "        else:\n",
    "            return s[::2].count('0')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, s: str) -> int:\n",
    "        count_0 = s.count('0')\n",
    "        count_1 = len(s) - count_0\n",
    "        \n",
    "        if abs(count_0 - count_1) > 1:\n",
    "            return -1\n",
    "        \n",
    "        target_0 = '01' * (len(s) // 2) + '0'\n",
    "        target_1 = '10' * (len(s) // 2) + '1'\n",
    "        \n",
    "        diff_0 = sum(1 for c, t in zip(s, target_0) if c != t)\n",
    "        diff_1 = sum(1 for c, t in zip(s, target_1) if c != t)\n",
    "        \n",
    "        if count_0 > count_1:\n",
    "            return diff_0 // 2\n",
    "        elif count_1 > count_0:\n",
    "            return diff_1 // 2\n",
    "        else:\n",
    "            return min(diff_0 // 2, diff_1 // 2)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, s: str) -> int:\n",
    "        s_list = [int(x) for x in s]\n",
    "        pos = sum(s_list)\n",
    "        neg = len(s_list) - pos\n",
    "        \n",
    "        diff = pos - neg\n",
    "        if len(s_list) < 2:\n",
    "            return 0\n",
    "        if abs(diff) > 1:\n",
    "            return -1\n",
    "        \n",
    "        counter1 = 0\n",
    "        counter2 = 0\n",
    "        for i, item in enumerate(s_list):\n",
    "            if i % 2 == 1 and item:\n",
    "                counter1 += 1\n",
    "            if i % 2 == 0 and item:\n",
    "                counter2 += 1      \n",
    "                     \n",
    "        if diff == 0:\n",
    "            if counter1 == len(s_list) // 2 or counter1 == 0:\n",
    "                return 0\n",
    "            return len(s_list) // 2 - max(counter1, counter2)\n",
    "\n",
    "        if diff > 0:\n",
    "            if not counter1:\n",
    "                return 0\n",
    "            return len(s_list) // 2 - counter2 + 1\n",
    "        else:\n",
    "            if not counter2:\n",
    "                return 0\n",
    "            return len(s_list) // 2 - counter1\n",
    "                    \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, s: str) -> int:\n",
    "        cnt = [0, 0]    # 第一位表示开头为1时不同的数量，第二位表示开头为0时不同的数量\n",
    "        c1 = 0\n",
    "        for i, c in enumerate(s):\n",
    "            # 偶数为1，给1加，偶数为0，给0加。奇数为1，给0加，奇数为0，给1加\n",
    "            cnt[i & 1 ^ int(c)] += 1\n",
    "            if c == '1':\n",
    "                c1 += 1\n",
    "\n",
    "        c0 = len(s) - c1\n",
    "        if abs(c1 - c0) > 1:\n",
    "            return -1\n",
    "        if c1 > c0:\n",
    "            diff = cnt[0]\n",
    "        elif c1 == c0:\n",
    "            diff = min(cnt)\n",
    "        else:\n",
    "            diff = cnt[1]\n",
    "        return diff + 1 >> 1\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, s: str) -> int:\n",
    "        diff = s.count('1')-s.count('0')\n",
    "        if diff>1 or diff <-1:\n",
    "            return -1\n",
    "        ans1 = len(s)\n",
    "        ans2 = len(s)\n",
    "        if diff >= 0 :\n",
    "            ans1 = sum([0 if i % 2==0 and s[i]==\"1\" or i % 2 == 1 and s[i]==\"0\" else 1 for i in range(len(s))])//2\n",
    "        if diff <= 0:\n",
    "            ans2 = sum([0 if i % 2==0 and s[i]==\"0\" or i % 2 == 1 and s[i]==\"1\" else 1 for i in range(len(s))])//2\n",
    "        \n",
    "        \n",
    "        return min(ans1,ans2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, s: str) -> int:\n",
    "\n",
    "        if abs(s.count('1') - s.count('0')) > 1:\n",
    "            return -1\n",
    "\n",
    "        ls = list(s)\n",
    "        n = len(ls)\n",
    "        if n % 2 == 0:\n",
    "            cnt1 = ls[1::2].count('1')\n",
    "            cnt2 = ls[::2].count('1')\n",
    "            res = min(int(n / 2) - cnt1, int(n / 2) - cnt2)\n",
    "        else:\n",
    "            if ls.count('1') > ls.count('0'):\n",
    "                res = int(n / 2) + 1 - ls[::2].count('1')\n",
    "            else:\n",
    "                res = int(n / 2) + 1 - ls[::2].count('0')\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, s: str) -> int:\n",
    "        zero,one = 0,0\n",
    "        for ch in s:\n",
    "            if ch=='0':\n",
    "                zero += 1\n",
    "            else:\n",
    "                one += 1\n",
    "\n",
    "        if abs(zero-one)>1:\n",
    "            return -1\n",
    "\n",
    "        res1,res2 = 0,0\n",
    "        # 101010..\n",
    "        for i in range(len(s)):\n",
    "            if i%2==0 and s[i]!='1':\n",
    "                res1 += 1\n",
    "            elif i%2==1 and s[i]!='0':\n",
    "                res1 += 1\n",
    "\n",
    "        if zero+1==one:\n",
    "            return res1//2\n",
    "                \n",
    "\n",
    "        # 010101..\n",
    "        for i in range(len(s)):\n",
    "            if i%2==0 and s[i]!='0':\n",
    "                res2 += 1\n",
    "            elif i%2==1 and s[i]!='1':\n",
    "                res2 += 1\n",
    "\n",
    "        if one+1==zero:\n",
    "            return res2//2\n",
    "\n",
    "        \n",
    "        return min(res1,res2)//2\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, s: str) -> int:\n",
    "        cnt_0 = s.count('0')\n",
    "        cnt_1 = s.count('1')\n",
    "        def check(x):\n",
    "            cnt = 0\n",
    "            for y in s[::2]:\n",
    "                cnt += int(y) ^ x\n",
    "            return cnt\n",
    "        if cnt_1 == 1 + cnt_0:\n",
    "            return check(1)\n",
    "        elif cnt_1 + 1 == cnt_0:\n",
    "            return check(0)\n",
    "        elif cnt_1 == cnt_0:\n",
    "            return min(check(0), check(1))\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, s: str) -> int:\n",
    "        cnt = [0, 0]    # 第一位表示开头为1时不同的数量，第二位表示开头为0时不同的数量\n",
    "        c1 = 0\n",
    "        for i, c in enumerate(s):\n",
    "            # 偶数为1，给1加，偶数为0，给0加。奇数为1，给0加，奇数为0，给1加\n",
    "            cnt[i & 1 ^ int(c)] += 1\n",
    "            if c == '1':\n",
    "                c1 += 1\n",
    "\n",
    "        c0 = len(s) - c1\n",
    "        if abs(c1 - c0) > 1:\n",
    "            return -1\n",
    "        if c1 > c0:\n",
    "            diff = cnt[0]\n",
    "        elif c1 == c0:\n",
    "            diff = min(cnt)\n",
    "        else:\n",
    "            diff = cnt[1]\n",
    "        return diff + 1 >> 1\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, s: str) -> int:\n",
    "        n=len(s)\n",
    "        c0=s.count('0')\n",
    "        c1=n-c0\n",
    "        if n%2==1:\n",
    "            if abs(c0-c1)!=1:\n",
    "                return -1\n",
    "            if c1>c0:\n",
    "                s1 = '1'+'01'*(n//2)\n",
    "            else:\n",
    "                s1 = '0'+'10'*(n//2)\n",
    "            return sum(1 for c1,c2 in zip(s, s1) if c1!=c2) // 2\n",
    "        # n is even\n",
    "        if c0!=c1:\n",
    "            return -1\n",
    "        s1='01'*(n//2)\n",
    "        d1 = sum(1 for c1,c2 in zip(s, s1) if c1!=c2)\n",
    "        return min(d1, n-d1) // 2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        cnt_0 = s.count('0')\n",
    "        cnt_1 = s.count('1')\n",
    "        if abs(cnt_0 - cnt_1) > 1: return -1\n",
    "        def check(s):\n",
    "            start = s[0]\n",
    "            cnt = 0\n",
    "            for i in range(0, n, 2):\n",
    "                if i != n-1:\n",
    "                    if s[i] == s[i+1]:\n",
    "                        if s[i] == start:\n",
    "                            cnt += 1\n",
    "                    else:\n",
    "                        if s[i] != start:\n",
    "                            cnt += 1\n",
    "                else:\n",
    "                    if s[i] != start:\n",
    "                        cnt += 1\n",
    "            return cnt\n",
    "        return min(check(s), check(s[::-1]))\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        cnt_0 = s.count('0')\n",
    "        cnt_1 = s.count('1')\n",
    "        if abs(cnt_0 - cnt_1) > 1: return -1\n",
    "        def check(x):\n",
    "            cnt = 0\n",
    "            for i in range(n):\n",
    "                cnt += int(s[i]) ^ x\n",
    "                x ^= 1\n",
    "            return cnt\n",
    "        if cnt_1 > cnt_0:\n",
    "            return check(1) // 2\n",
    "        elif cnt_1 < cnt_0:\n",
    "            return check(0) // 2\n",
    "        return min(check(0), check(1)) // 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, s: str) -> int:\n",
    "        cnt1, cnt2 = 0, 0\n",
    "        print(len(s))\n",
    "        if len(s)%2 == 0:\n",
    "            if Counter(s)['1'] != Counter(s)['0']:\n",
    "                return -1\n",
    "            else:\n",
    "                for i in range(0, len(s)-1, 2):\n",
    "                    if s[i] == '0':\n",
    "                        cnt1 += 1\n",
    "                    else:\n",
    "                        cnt2 += 1\n",
    "                return min(cnt1, cnt2)\n",
    "        if len(s)%2 == 1:\n",
    "            cnt3, cnt4 = 0, 0\n",
    "            if abs(Counter(s)['1'] - Counter(s)['0']) != 1:\n",
    "                return -1\n",
    "            else:\n",
    "                for i in range(0, len(s), 2):\n",
    "                    if s[i] == '0':\n",
    "                        cnt1 += 1\n",
    "                    else:\n",
    "                        cnt2 += 1\n",
    "                for i in range(1, len(s)-1, 2):\n",
    "                    if s[i] == '0':\n",
    "                        cnt3 += 1\n",
    "                    else:\n",
    "                        cnt4 += 1\n",
    "                if cnt1 == cnt4:\n",
    "                    return cnt1\n",
    "                else:\n",
    "                    return cnt2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        n0, n1 = s.count('0'), s.count('1')\n",
    "        res = float(\"INF\")\n",
    "        # \"1010...\"\n",
    "        if n1 == (n + 1) // 2 and n0 == n // 2:   # 不同字符个数相等\n",
    "            diff1 = 0\n",
    "            for i in range(n):\n",
    "                if int(s[i]) == i % 2:   # 对应位数不同\n",
    "                    diff1 += 1\n",
    "            res = min(res, diff1 // 2)\n",
    "        # \"0101...\"\n",
    "        if n0 == (n + 1) // 2 and n1 == n // 2:   # 不同字符个数相等\n",
    "            diff2 = 0\n",
    "            for i in range(n):\n",
    "                if int(s[i]) != i % 2:   # 对应位数不同\n",
    "                    diff2 += 1\n",
    "            res = min(res, diff2 // 2)\n",
    "        if res == float(\"INF\"):\n",
    "            return -1   # 不存在\n",
    "        else:\n",
    "            return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, s: str) -> int:\n",
    "        if abs(s.count('0')-s.count('1'))>1:\n",
    "            return -1\n",
    "        table = [0,1]\n",
    "        n = len(s)\n",
    "        pat = \"\"\n",
    "        for i in range(n):\n",
    "            pat = pat +str(table[i%2])\n",
    "        ans1 = 0\n",
    "        for i in range(n):\n",
    "            if pat[i]!=s[i]:\n",
    "                ans1 += 1\n",
    "        ans1 = ans1//2 if ans1%2==0 else inf\n",
    "        pat = \"\"\n",
    "        for i in range(n):\n",
    "            pat = pat +str(table[(i+1)%2])\n",
    "        ans2 = 0\n",
    "        for i in range(n):\n",
    "            if pat[i]!=s[i]:\n",
    "                ans2 += 1\n",
    "        ans2 = ans2//2 if ans2%2==0 else inf\n",
    "        return min(ans1,ans2) if min(ans1,ans2)!=0 else 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, s: str) -> int:\n",
    "        one_even, one_odd = 0 , 0\n",
    "        zero_even, zero_odd = 0, 0\n",
    "        for i, x in enumerate(s):\n",
    "            if x == \"1\":\n",
    "                if i % 2 == 0:\n",
    "                    one_even += 1\n",
    "                else:\n",
    "                    one_odd += 1\n",
    "            else:\n",
    "                if i % 2 == 0:\n",
    "                    zero_even += 1\n",
    "                else:\n",
    "                    zero_odd += 1\n",
    "        if abs(one_even + one_odd - zero_even - zero_odd) > 1:\n",
    "            return -1\n",
    "        elif one_even + one_odd - zero_even - zero_odd == 1:\n",
    "            return one_odd\n",
    "        elif one_even + one_odd - zero_even - zero_odd == -1:\n",
    "            return zero_odd\n",
    "        else:\n",
    "            return min(one_even, one_odd)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        cnt = sum(x=='1' for x in s)\n",
    "        if abs(n-cnt -cnt) >1:\n",
    "            return -1\n",
    "        \n",
    "        def f(s2:str):\n",
    "            nonlocal cnt\n",
    "            d =0 \n",
    "            cnt2 = sum(x=='1' for x in s2)\n",
    "            if cnt2 != cnt:\n",
    "                return inf\n",
    "\n",
    "            for x,y in zip(s,s2):\n",
    "                # print(x,y)\n",
    "                d += (x!=y)\n",
    "            print(d)\n",
    "            return d\n",
    "\n",
    "        return min(f(('01'*n)[:n]),f(('10'*n)[:n]))//2\n",
    "         \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, s: str) -> int:\n",
    "        cnt = [0, 0]    # 第一位表示开头为1时不同的数量，第二位表示开头为0时不同的数量\n",
    "        c1 = 0\n",
    "        for i, c in enumerate(s):\n",
    "            # 偶数为1，给1加;偶数为0，给0加\n",
    "            # 奇数为1，给0加;奇数为0，给1加\n",
    "            cnt[i & 1 ^ (c == '1')] += 1\n",
    "            if c == '1':\n",
    "                c1 += 1\n",
    "\n",
    "        c0 = len(s) - c1\n",
    "        if abs(c1 - c0) > 1:\n",
    "            return -1\n",
    "        if c1 > c0:\n",
    "            diff = cnt[0]\n",
    "        elif c1 == c0:\n",
    "            diff = min(cnt)\n",
    "        else:\n",
    "            diff = cnt[1]\n",
    "        return diff + 1 >> 1\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, s: str) -> int:\n",
    "        cnt0, cnt1 = s.count('0'), s.count('1')\n",
    "        n = len(s)\n",
    "        if not ((n % 2 and abs(cnt0 - cnt1) == 1) or (n % 2 == 0 and cnt0 == cnt1)):\n",
    "            return -1 \n",
    "        \n",
    "        \n",
    "        t1 = '01' * (n // 2)\n",
    "        t2 = '10' * (n // 2)\n",
    "        if n % 2:\n",
    "            t1 += '0'\n",
    "            t2 += '1'\n",
    "        ans = n\n",
    "        c1 = sum(a != b for a, b in zip(s, t1))\n",
    "        if c1 % 2 == 0: ans = min(ans, c1 // 2)\n",
    "        c2 = sum(a != b for a, b in zip(s, t2))\n",
    "        if c2 % 2 == 0: ans = min(ans, c2 // 2)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, s: str) -> int:\n",
    "        cnt = [0, 0]    # 第一位表示开头为1时不同的数量，第二位表示开头为0时不同的数量\n",
    "        c1 = 0\n",
    "        for i, c in enumerate(s):\n",
    "            # 偶数为1，给1加;偶数为0，给0加\n",
    "            # 奇数为1，给0加;奇数为0，给1加\n",
    "            cnt[i & 1 ^ int(c)] += 1\n",
    "            if c == '1':\n",
    "                c1 += 1\n",
    "\n",
    "        c0 = len(s) - c1\n",
    "        if abs(c1 - c0) > 1:\n",
    "            return -1\n",
    "\n",
    "        if c1 > c0:\n",
    "            diff = cnt[0]\n",
    "        elif c1 == c0:\n",
    "            diff = min(cnt)\n",
    "        else:\n",
    "            diff = cnt[1]\n",
    "        return diff + 1 >> 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        one_cnt = s.count('1')\n",
    "        if abs(one_cnt - (n - one_cnt)) >= 2:\n",
    "            return -1\n",
    "\n",
    "        # 奇数 1\n",
    "        one_cnt1, zero_cnt1 = 0, 0\n",
    "        for i in range(n):\n",
    "            if i % 2 == 0 and s[i] != '0':\n",
    "                zero_cnt1 += 1\n",
    "            if i % 2 and s[i] != '1':\n",
    "                one_cnt1 += 1\n",
    "        cnt1 = one_cnt1 if one_cnt1 == zero_cnt1 else inf\n",
    "        # 偶数1\n",
    "        one_cnt2, zero_cnt2 = 0, 0\n",
    "        for i in range(n):\n",
    "            if i % 2 == 0 and s[i] != '1':\n",
    "                one_cnt2 += 1\n",
    "            if i % 2 and s[i] != '0':\n",
    "                zero_cnt2 += 1\n",
    "        cnt2 = one_cnt2 if one_cnt2 == zero_cnt2 else inf\n",
    "        return min(cnt1, cnt2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, s: str) -> int:\n",
    "        import math\n",
    "        num1 = s.count('1')\n",
    "        num0 = s.count('0')\n",
    "        if abs(num1 - num0) > 1:\n",
    "            return -1\n",
    "        n = len(s)\n",
    "        valid_s = []\n",
    "        if n % 2 == 0:\n",
    "            valid_s.append('10' * num0)\n",
    "            valid_s.append('01' * num0)\n",
    "        else:\n",
    "            if num1 > num0:\n",
    "                valid_s.append('10' * num0 + '1')\n",
    "            else:\n",
    "                valid_s.append('01' * num0 + '0')\n",
    "        ans = math.inf\n",
    "        # print(valid_s)\n",
    "        for val_s in valid_s:\n",
    "            cnt = sum(val_s[i] != s[i] for i in range(n))\n",
    "            ans = min(ans, cnt//2)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        cnt0 = s.count('0')\n",
    "        cnt1 = n - cnt0\n",
    "        if abs(cnt0 - cnt1) > 1:\n",
    "            return -1\n",
    "        c1 = '0'\n",
    "        c2 = '1'\n",
    "        k1 = k2 = 0\n",
    "        if n % 2:\n",
    "            if cnt1 > cnt0:\n",
    "                c1 = '1'\n",
    "                c2 = '0'\n",
    "            for i in range(0, n, 2):\n",
    "                if i == n - 1:\n",
    "                    k1 += (s[i] != c1)\n",
    "                else:\n",
    "                    k1 += (s[i] != c1) + (s[i + 1] != c2)\n",
    "            return k1 // 2\n",
    "        else:\n",
    "            for i in range(0, n, 2):\n",
    "                k1 += (s[i] != c1) + (s[i + 1] != c2)\n",
    "                k2 += (s[i] != c2) + (s[i + 1] != c1)\n",
    "            return min(k1 // 2, k2 // 2)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, s: str) -> int:\n",
    "        num0, num1 = 0, 0\n",
    "        for c in s:\n",
    "            if c == '0':\n",
    "                num0 += 1\n",
    "            else:\n",
    "                num1 += 1\n",
    "        if abs(num0 - num1) > 1:\n",
    "            return -1\n",
    "        ans = 0\n",
    "        n = len(s)\n",
    "        if num1 > num0:\n",
    "            for i in range(0, n, 2):\n",
    "                    if s[i] != '1':\n",
    "                        ans += 1\n",
    "        elif num0 > num1:\n",
    "            for i in range(0, n, 2):\n",
    "                if s[i] != '0':\n",
    "                    ans += 1\n",
    "        else:\n",
    "            for i in range(0, n, 2):\n",
    "                    if s[i] != '1':\n",
    "                        ans += 1\n",
    "            tmp = 0\n",
    "            for i in range(0, n, 2):\n",
    "                if s[i] != '0':\n",
    "                    tmp += 1\n",
    "            ans = min(ans, tmp)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, s: str) -> int:\n",
    "        num0=0\n",
    "        num1=0\n",
    "        for s0 in s:\n",
    "            if s0==\"1\":\n",
    "                num1+=1\n",
    "            else:\n",
    "                num0+=1\n",
    "        n=len(s)\n",
    "        print(num0,num1)\n",
    "        if n%2==0:\n",
    "            if num0!=num1:\n",
    "                return -1\n",
    "        if n%2==1:\n",
    "            if abs(num0-num1)>1:\n",
    "                return -1\n",
    "        cnt=0\n",
    "        cnt1=0\n",
    "        for i in range(0,n,2):\n",
    "                if s[i]!=\"1\":\n",
    "                    cnt+=1\n",
    "        for i in range(1,n,2):\n",
    "            if s[i]!=\"1\":\n",
    "                cnt1+=1\n",
    "        if num0==num1:\n",
    "            return min(cnt1,cnt)\n",
    "        if num0>num1:\n",
    "            return cnt1\n",
    "        else:\n",
    "            return cnt\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution():\n",
    "\tdef minSwaps(self, s: str) -> int:\n",
    "\t\tz=o=0\n",
    "\t\tfor c in s:\n",
    "\t\t\tif c==\"0\":\n",
    "\t\t\t\tz+=1\n",
    "\t\t\telse:\n",
    "\t\t\t\to+=1\n",
    "\t\tif abs(z-o)>1:\n",
    "\t\t\treturn -1\n",
    "\t\tif z>o:\n",
    "\t\t\tcur=0\n",
    "\t\telse:\n",
    "\t\t\tcur=1\n",
    "\t\tw=0\n",
    "\t\tfor c in s:\n",
    "\t\t\tif int(c) != cur:\n",
    "\t\t\t\tw+=1\n",
    "\t\t\tcur=abs(cur-1)\n",
    "\t\tif z==o:\n",
    "\t\t\tcur=0\n",
    "\t\t\tw2=0\n",
    "\t\t\tfor c in s:\n",
    "\t\t\t\tif int(c) != cur:\n",
    "\t\t\t\t\tw2+=1\n",
    "\t\t\t\tcur=abs(cur-1)\n",
    "\t\t\treturn min(w//2,w2//2)\n",
    "\t\treturn w//2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, s: str) -> int:\n",
    "        # 如果1个数比0个数多1，那么目标是101010，如果0比1多1，目标是01010，不同位数//2\n",
    "        # 如果0和1个数相同，那么需要考虑哪种情况操作少\n",
    "        cnt1,cnt0=s.count('1'),s.count('0')\n",
    "        if cnt1+1==cnt0:\n",
    "            cnt=0\n",
    "            for i,c in enumerate(s):\n",
    "                if i%2==0 and c=='1':\n",
    "                    cnt+=1\n",
    "                elif i%2==1 and c=='0':\n",
    "                    cnt+=1\n",
    "            return cnt//2\n",
    "        elif cnt1-1==cnt0:\n",
    "            cnt=0\n",
    "            for i,c in enumerate(s):\n",
    "                if i%2==0 and c=='0':\n",
    "                    cnt+=1\n",
    "                elif i%2==1 and c=='1':\n",
    "                    cnt+=1\n",
    "            return cnt//2\n",
    "        elif cnt0==cnt1:\n",
    "            ans=inf\n",
    "            c1,c2=0,0\n",
    "            for i,c in enumerate(s):\n",
    "                if i%2==0 and c=='0':\n",
    "                    c1+=1\n",
    "                elif i%2==1 and c=='1':\n",
    "                    c1+=1\n",
    "                elif i%2==0 and c=='1':\n",
    "                    c2+=1\n",
    "                elif i%2==1 and c=='0':\n",
    "                    c2+=1\n",
    "            # print(c1,c2,ans)\n",
    "            ans=min(ans,c1//2,c2//2)\n",
    "            return ans \n",
    "        else:\n",
    "            return -1\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, s: str) -> int:\n",
    "        a = b = 0\n",
    "        c = d = 0\n",
    "        for i in range(len(s)):\n",
    "            if s[i] == str(i%2):\n",
    "                b += 1\n",
    "            else:\n",
    "                a += 1\n",
    "            if s[i] == '0':\n",
    "                c += 1\n",
    "            else:\n",
    "                d += 1\n",
    "                \n",
    "\n",
    "        \n",
    "        if max(c, d) - min(c, d) > 1:\n",
    "            return -1\n",
    "            \n",
    "        if a % 2 == 1 and b % 2 == 1:\n",
    "            return -1\n",
    "        \n",
    "        if a % 2 == 1:\n",
    "            return b//2\n",
    "        \n",
    "        if b % 2 == 1:\n",
    "            return a//2\n",
    "\n",
    "        \n",
    "       \n",
    "\n",
    "        return min(a//2, b//2)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, s: str) -> int:\n",
    "        cnt_0 = s.count('0')\n",
    "        cnt_1 = s.count('1')\n",
    "        tmp = list(map(int, s))\n",
    "        def check(x):\n",
    "            cnt = 0\n",
    "            for y in tmp[::2]:\n",
    "                cnt += y ^ x\n",
    "            return cnt\n",
    "        if cnt_1 == 1 + cnt_0:\n",
    "            return check(1)\n",
    "        elif cnt_1 + 1 == cnt_0:\n",
    "            return check(0)\n",
    "        elif cnt_1 == cnt_0:\n",
    "            return min(check(0), check(1))\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        ans = n\n",
    "        cnt_0, cnt_1 = s.count('0'), s.count('1')\n",
    "        if abs(cnt_0 - cnt_1) > 1: return -1\n",
    "        if cnt_0 == cnt_1:\n",
    "            tmp1, tmp2 = '0', '1'\n",
    "            cnt1, cnt2 = 0, 1\n",
    "            for i in range(1, n):\n",
    "                tmp1 += str(1 - cnt1)\n",
    "                tmp2 += str(1 - cnt2)\n",
    "                cnt1, cnt2 = 1 - cnt1, 1 - cnt2\n",
    "            cnt = 0\n",
    "            for x, y in zip(s, tmp1):\n",
    "                if x != y: cnt += 1\n",
    "\n",
    "            ans = min(ans, cnt // 2)\n",
    "            cnt = 0\n",
    "            for x, y in zip(s, tmp2):\n",
    "                if x != y: cnt += 1\n",
    "\n",
    "            ans = min(ans, cnt // 2)\n",
    "        elif cnt_0 > cnt_1:\n",
    "            tmp1 = '0'\n",
    "            cnt1 = 0\n",
    "            for i in range(1, n):\n",
    "                tmp1 += str(1 - cnt1)\n",
    "                cnt1 = 1 - cnt1\n",
    "            cnt = 0\n",
    "            for x, y in zip(s, tmp1):\n",
    "                if x != y: cnt += 1\n",
    "\n",
    "            ans = min(ans, cnt // 2)\n",
    "        else:\n",
    "            tmp1 = '1'\n",
    "            cnt1 = 1\n",
    "            for i in range(1, n):\n",
    "                tmp1 += str(1 - cnt1)\n",
    "                cnt1 = 1 - cnt1\n",
    "            cnt = 0\n",
    "            for x, y in zip(s, tmp1):\n",
    "                if x != y: cnt += 1\n",
    "                \n",
    "            ans = min(ans, cnt // 2)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, s: str) -> int:\n",
    "        num0 = 0\n",
    "        num1 = 0\n",
    "        for ch in s:\n",
    "            if ch == '1':\n",
    "                num1 += 1\n",
    "            else:\n",
    "                num0 += 1\n",
    "        if int(abs(num0 - num1)) > 1:\n",
    "            return -1\n",
    "        odd0 = 0\n",
    "        odd1 = 0\n",
    "        for i in range(len(s)):\n",
    "            if i % 2 != 0:\n",
    "                if s[i] == '0':\n",
    "                    odd0 += 1\n",
    "                else:\n",
    "                    odd1 += 1\n",
    "        if len(s) % 2 == 0:\n",
    "            return min(odd0, odd1)\n",
    "        else:\n",
    "            if num0 > num1:\n",
    "                return odd0\n",
    "            else:\n",
    "                return odd1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        ans = inf\n",
    "        diff = 0\n",
    "        n0, n1 = s.count('0'), s.count('1')\n",
    "        if n0 == (n + 1) // 2 and n1 == n // 2:\n",
    "            for i in range(n):\n",
    "                if int(s[i]) != i % 2:\n",
    "                    diff += 1\n",
    "            ans = min(ans, diff // 2)\n",
    "        diff = 0\n",
    "        if n1 == (n + 1) // 2 and n0 == n // 2:\n",
    "            for i in range(n):\n",
    "                if int(s[i]) == i % 2:\n",
    "                    diff += 1\n",
    "            ans = min(ans, diff // 2)\n",
    "        return ans if ans != inf else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, s: str) -> int:\n",
    "        cnt0 = s.count('0')\n",
    "        cnt1 = len(s) - cnt0\n",
    "        delta = abs(cnt0 - cnt1)\n",
    "        ans = 0\n",
    "        res = 0\n",
    "        if delta >= 2:\n",
    "            return -1\n",
    "        else:\n",
    "            for i in range(0, len(s), 2):\n",
    "                if s[i] == '1':\n",
    "                    ans += 1\n",
    "                else:\n",
    "                    res += 1\n",
    "            if cnt0 > cnt1:\n",
    "                return ans\n",
    "            elif cnt0 == cnt1:\n",
    "                return min(ans, res)\n",
    "            else:\n",
    "                return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        one_cnt = s.count('1')\n",
    "        if abs(one_cnt - (n - one_cnt)) >= 2:\n",
    "            return -1\n",
    "        # 10101\n",
    "        zero_cnt1, one_cnt1 = 0, 0\n",
    "        for i in range(n):\n",
    "            if not i % 2 and s[i] != '1':\n",
    "                zero_cnt1 += 1\n",
    "            if i % 2 and s[i] != '0':\n",
    "                one_cnt1 += 1\n",
    "        cnt1 = one_cnt1 if one_cnt1 == zero_cnt1 else inf\n",
    "        # 01010\n",
    "        zero_cnt2, one_cnt2 = 0, 0\n",
    "        for i in range(n):\n",
    "            if not i % 2 and s[i] != '0':\n",
    "                one_cnt2 += 1\n",
    "            if i % 2 and s[i] != '1':\n",
    "                zero_cnt2 += 1\n",
    "        cnt2 = one_cnt2 if one_cnt2 == zero_cnt2 else inf\n",
    "        return min(cnt1, cnt2)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        cnt_0 = s.count('0')\n",
    "        cnt_1 = s.count('1')\n",
    "        if abs(cnt_0 - cnt_1) > 1: return -1\n",
    "        def check(s):\n",
    "            start = s[0]\n",
    "            cnt = 0\n",
    "            for i in range(0, n, 2):\n",
    "                if i != n-1:\n",
    "                    if s[i] == s[i+1]:\n",
    "                        if s[i] == start:\n",
    "                            cnt += 1\n",
    "                    else:\n",
    "                        if s[i] != start:\n",
    "                            cnt += 1\n",
    "                else:\n",
    "                    if s[i] != start:\n",
    "                        cnt += 1\n",
    "            return cnt\n",
    "        return min(check(s), check(s[::-1]))\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        cnt_0 = s.count('0')\n",
    "        cnt_1 = n - cnt_0\n",
    "        if abs(cnt_0 - cnt_1) > 1: return -1\n",
    "        tmp = list(map(int, s))\n",
    "        def check(x):\n",
    "            cnt = 0\n",
    "            for i in range(n):\n",
    "                cnt += tmp[i] ^ x\n",
    "                x ^= 1\n",
    "            return cnt\n",
    "        if cnt_1 > cnt_0:\n",
    "            return check(1) // 2\n",
    "        elif cnt_1 < cnt_0:\n",
    "            return check(0) // 2\n",
    "        return min(check(0), check(1)) // 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, s: str) -> int:\n",
    "        c = Counter(s)\n",
    "        if abs(c['0'] - c['1']) > 1: return -1\n",
    "        if len(s) % 2 == 0:\n",
    "            res = sum([1 if (i % 2 == 0 and s[i] == '0') else 0 for i in range(len(s))])\n",
    "            return min(res, len(s) // 2 - res)\n",
    "        else:\n",
    "            key = '0' if c['0'] > c['1'] else '1'\n",
    "            res = sum([1 if (i % 2 == 0 and s[i] != key) else 0 for i in range(len(s))])\n",
    "            return res"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
